package experiment5;

/**
 * @author mazouri
 * @create 2021-11-18 11:40
 */
public class MaxSubArray {
    static int maxSeq(int[] v, int left, int right) {
        if (left > right) return 0;
        int mid = (left + right) / 2;
        //不包含中间元素
        int leftMax = maxSeq(v, left, mid - 1);  //不包含中间元素
        int rightMax = maxSeq(v, mid + 1, right);  //Y中间元素往右
        int max1 = v[mid];
        int sum = v[mid];
        for (int i = mid + 1; i <= right; i++) {
            sum += v[i];
            if (max1 < sum) max1 = sum;
        }
        //中间元素往左
        int max2 = v[mid];
        sum = v[mid];
        for (int i = mid - 1; i >= left; i--) {
            sum += v[i];
            if (max2 < sum) max2 = sum;
        }
        int midMax = max1 + max2 - v[mid];
        return Math.max(leftMax, Math.max(midMax, rightMax));
    }

    public static void main(String[] args) {
//        int[] v = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] v = {4,-3,5,-2,-1,2,6,-2};
        int max = maxSeq(v, 0, 7);
        System.out.println(max);
    }

}
